g) (30 bodov)

S ďalšou úlohou prišlo personálne oddelenie. Práve sa dáva dokopy výprava, ktorá má ísť preskúmať neznáme končiny vesmíru. Posádku tejto lode bude tvoriť niekoľko členov, ktorí sú výnimoční špecialisti v mnohých činnostiach, potrebných na takej dôležitej a nebezpečnej výprave. Presnejšie, existuje M (1 <= M <= 20) možných vecí, v ktorých môže byť človek odborník. Na konkurz sa prihlásilo N (1 <= N <= 15) kandidátov a každý z týchto kandidátov je špecialista v niektorých z týchto činností. Úlohou personálneho oddelenia je zostaviť posádku tak, aby sa v nej nachádzal aspoň jeden špecialista v každej činnosti. Rozpočet projektu ale nie je neobmedzený. Každý člen dostane rovnaký plat a preto chce personálne oddelenie spomedzi uchádzačov zostaviť čo najmenej početnú skupinu. Napíšte program, ktorý bude uvedené skupiny zostavovať.

Na vstupe bude v prvom riadku číslo M. Nasleduje M riadkov, na každej je jeden reťazec znakov, pomenúvavajúci príslušnú činnosť špecializácie. Na ďalšom riadku je číslo N a za ním nasleduje popis N uchádzačov. Popis uchádzača začína kladným celým číslom x (medzi 1 a M vrátane): počet špecializácii, ktoré ovláda a pokračuje menom uchádzača. Na ďalších x riadkoch je na každom jedna zo špecializácii uvedených na začiatku vstupu. Mená špecializácii aj mená kandidátov sú reťazce znakov malej a veľkej anglickej abecedy. Ich dĺžka je medzi 1 a 40. Neobsahujú medzery ani žiadne iné znaky. Všetky názvy činností a tiež mená uchádzačov sú rôzne.

Na jedinom riadku výstupu vypíšte medzerami oddelený zoznam mien, ktoré tvoria posádku. Táto posádka musí pre každú potrebnú špecializáciu obsahovať niekoho, kto ju ovláda. Spomedzi všetkých takých posádok musí byť najmenšia možná. Ak je stále možností viac, tak musí pozostávať z mien, ktoré sú lexikograficky najmenšie (viď nižšie). Zoznam členov vypíšte utriedený lexikograficky. Môžete predpokladať, že existuje nejaká zostaviteľná posádka (teda, že každú špecializáciu ovláda aspoň jeden uchádzač).

Usporiadanie písmen je obvyklé abecedné, najskôr sú všetky veľké písmená a za nimi nasledujú všetky malé písmená (teda, A je v našom usporiadaní skôr ako Z, ktoré je ale skôr ako a). Pre dve rôzne slová u a v platí, že slovo u je v lexikografickom usporiadaní skôr ako slovo v vtedy, ak prvé písmeno, ktorom sa líšia, je v slove u menšie. Ak také písmeno neexistuje, potom je lexikograficky skôr slovo, ktoré je kratšie. Dve rôzne rovnako početné množiny slov sa porovnávajú tak, že sa najprv obe usporiadajú lexikograficky a potom sa porovnáva prvé slovo z jednej množiny a prvé slovo z druhej množiny. Ak sa tieto rovnajú, pokračuje sa druhým slovom a tak ďalej. Časový limit v tejto úlohe sú 2 sekundy.

Príklad:

Vstup:

3
ZabijacSvabov
ZdobicMedovnikov
BankarVMonopolach
3
2 Zemco
ZabijacSvabov
ZdobicMedovnikov
1 Misof
BankarVMonopolach
2 Mic
BankarVMonopolach
ZabijacSvabov

Výstup:

Mic Zemco

Poznámka:

Jednočlennú posádku nedokážeme zostaviť, pretože nikto nemá všetky tri potrebné špecializácie. Pri dvojčlenných posádkach máme možnosti Mic a Zemčo alebo Mišof a Zemčo, z ktorých je prvá lexikograficky menšia.

Vstup:

3
StruhacCeruziek
VysavacKobercov
FukacBubliniek
4
2 Dalibor
StruhacCeruziek
VysavacKobercov
1 Bob
VysavacKobercov
1 Cecilia
StruhacCeruziek
1 Eva
FukacBubliniek

Výstup:

Dalibor Eva

Poznámka:

Evu treba určite zobrať, lebo ako jediná vie fúkať bublinky. K nej môžeme zobrať Cecíliu a Boba, ktorí vedia zvyšné dve činnosti. Lacnejšie je ale zobrať samého Dalibora.

Vstup:

2
BalicDarcekov
RozbalovacDarcekov
3
1 a
BalicDarcekov
2 aa
RozbalovacDarcekov
BalicDarcekov
2 aaa
BalicDarcekov
RozbalovacDarcekov

Výstup:

aa

Poznámka:

Je zjavné, že dokážeme zostaviť jednočlennú posádku. Uchádzač a do nej ale patriť nemôže. Spomedzi zvyšných dvoch uchádzačov je skôr v abecede aa.

---